/*
 * @lc app=leetcode.cn id=958 lang=typescript
 *
 * [958] 二叉树的完全性检验
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * class TreeNode {
 *     val: number
 *     left: TreeNode | null
 *     right: TreeNode | null
 *     constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
 *         this.val = (val===undefined ? 0 : val)
 *         this.left = (left===undefined ? null : left)
 *         this.right = (right===undefined ? null : right)
 *     }
 * }
 */

function countNodes(node: TreeNode | null): number {
  if (node === null) return 0;
  return countNodes(node.left) + countNodes(node.right) + 1;
}

function judge(node: TreeNode | null, n: number, m: number): boolean {
  // 没有节点了，判断节点总数是否等于0
  if (node === null) return n === 0;
  // 总数1，最后一个必须是叶子节点
  if (n === 1) return node.left === null && node.right === null;
  // 总数0，但还有节点，只能返回false
  if (n === 0) return false;
  // 除了最后一层，剩余的节点总数
  const k = 2 * m - 1;
  // 下一层左节点的总数
  const l = Math.min(n - k, m);
  // 下一层右节点的总数
  const r = n - k - l;
  // 递归判断左右节点的数量是否符合完全二叉树特性
  return (
    judge(node.left, ((k - 1) >> 1) + l, m >> 1) && judge(node.right, ((k - 1) >> 1) + r, m >> 1)
  );
}

function isCompleteTree(root: TreeNode | null): boolean {
  // 总共有多少个节点
  const n = countNodes(root);
  // 倒数第二层有几个节点
  let m = 1;
  // n层的总结点数
  let k = 1;
  while (k + 2 * m <= n) {
    m *= 2;
    k += m;
  }

  return judge(root, n, m);
}
// @lc code=end
